#include <boost/numeric/ublas/matrix.hpp>
using namespace boost::numeric::ublas;
template<typename T>
class WeightedGraph{
public :
	WeightedGraph<T>(int size);
	~WeightedGraph<T>();
	void addVertex(int count);
	void addArc(int i, int j, T arcWeight);
	T getArc(int i, int j);
	int getSize();
	void removeArc(int i, int j);
	void removeVertex(int position);
	matrix<T>* get_shortest_ranges();
	matrix<T>* m;

};

template<typename T>
WeightedGraph<T>::WeightedGraph(int size):
    m(new boost::numeric::ublas::matrix<T>(size, size)) {
	for (int i=0; i<size; i++){
		for(int j=0; j<size; j++){
			m->insert_element(i,j,100000);
		}
	}

}

template<typename T>
WeightedGraph<T>::~WeightedGraph<T>(){
	delete m;
}

template<typename T> 
matrix<T>* WeightedGraph<T>::get_shortest_ranges(){
	int n = m->size1();
	matrix<T>* D = new matrix<T>(n,n);

	for(int i=0; i<n; i++){
		for(int j=0; j<n; j++){
			D->insert_element(i,j,(*m)(i,j));
		}
	}

	
	for (int k=0; k<n; k++){
		for(int i=0; i<n; i++){
			for(int j=0; j<n; j++)
			{
				if ((*D)(i,j)>(*D)(i,k)+(*D)(k,j))
					(*D)(i,j) = (*D)(i,k)+(*D)(k,j);
			}
		}
	}
	return D;
}
template<typename T> 
int WeightedGraph<T>::getSize(){
	return m->size1();
}
template<typename T> 
void WeightedGraph<T>::addVertex(int count){
	int m_size = m->size1();
	m_size+=count;
	m->resize(m_size,m_size,true);
}

template<typename T> 
void WeightedGraph<T>::addArc(int i, int j, T arcWeight){
	m->erase_element(i,j);
	m->insert_element(i,j,arcWeight);
}

template<typename T> 
T WeightedGraph<T>::getArc(int i, int j){
	return (*m)(i,j);
}